Video systems are known to include a plurality of communication devices and communication channels, which provide the communication medium for the communication devices. For example, the communication channel may be wireline connections or RF frequency carriers. To increase the efficiency of the video system, video that needs to be communicated is digitally compressed. The digital compression reduces the number of bits needed to represent the video while maintaining perceptual quality of the video. The reduction in bits allows more efficient use of channel bandwidth and reduces storage requirements. To achieve digital video compression, each communication device may include an encoder and a decoder. The encoder allows a communication device to compress video before transmission over a communication channel. The decoder enables the communication device to receive compressed video from a communication channel and render it visible. Communication devices that may use digital video compression include high definition television transmitters and receivers, cable television transmitters and receivers, video telephones, computers and portable radios.
Several standards for digital video compression have emerged, including International Telecommunications Union (ITU) -T Recommendation H.261, the International Standards Organization/ International Electrotechnical Committee (ISO/IEC) 11172-2 International Standard (MPEG-1), and the forthcoming ISO/IEC 13818-2 standard (MPEG-2). These standards seek to efficiently represent a sequence of frames of video by exploiting the spatial and temporal redundancies in the video and by taking advantage of the perceptual qualities of the human eye. Temporal redundancy is exploited by estimating the motion in a sequence of frames.
Block matching algorithms are a known method for estimating motion within a video sequence. Each frame of the video sequence is divided into blocks of pixels. Block matching algorithms compare a current block that is to be encoded in one frame with blocks of the same size in a previous or future frame of the video sequence. Once a matching block is found in a frame that has previously been encoded, then a decision must be made whether to encode the current block independently or whether to encode the location of the matching block and any differences between the current block and the matching block. This decision is commonly referred to as the intra/non-intra decision. If the current block is coded independently then intra coding is selected. If the location of the matching block and the differences between the current block and the matching block are encoded, then non-intra coding is selected. Encoding only the location and any difference information may provide a more efficient method of encoding.
The intra/non-intra decision tries to determine whether the current block or the difference between the current block and the matching block will be more efficient to encode. Since there are several steps beyond the intra/non-intra decision that actually determine the number of bits, i.e., efficiency of the coding, this decision is complex. To most accurately predict which encoding method is most efficient, both an intra coded and non-intra coded block would have to be encoded and a comparison of the resulting number of bits made. However, this solution requires duplicate hardware to simultaneously do both modes of encoding. This may be impractical.
Another method for determining whether to intra code or non-intra code is to calculate for each pixel in the current block, the absolute value of the difference between the average pixel value and each pixel value in the current block and then sum the values. This sum is referred to as the sum of absolute differences (SOAD) for the current block. Similarly, the sum of the absolute values of the difference between each pixel in the matching block and each pixel in the current block is calculated. This sum is referred to as the sum of absolute differences (SOAD) for the difference block. If the SOAD for the difference block is less than or equal to a certain threshold, non-intra coding is chosen. Otherwise, if the SOAD for the difference block is greater than the threshold and greater than the SOAD for the current block, then intra coding is chosen. The SOAD calculation for the current block requires for a 16 pixel by 16 pixel (16.times.16) video block approximately 1024 operations. For a common video sequence of 396 blocks per frame and 30 frames per second, the cost of the SOAD for the current block alone is more than 12 million operations per second. This cost is very high. However, if a careful determination of whether to intra code or non-intra code isn't made, the quality of the video is sacrificed.
Therefore, a need exists to reduce the number of operations needed to determine whether to intra code or non-intra code a video block, yet provide adequate video quality.